//class Solution {
//public:
//    int trap(vector<int>& height) {
//        if (height.size() < 2)
//            return 0;
//        int ret = 0;
//        stack<int> st;
//        st.push(0);
//        for (int i = 1; i < height.size(); i++) {
//            while (!st.empty() && height[i] > height[st.top()]) {
//                int mid = height[st.top()];  st.pop();
//                if (!st.empty()) {
//                    int h = min(height[st.top()], height[i]) - mid;
//                    int w = i - st.top() - 1;
//                    ret += h * w;
//                }
//            }
//            st.push(i);
//        }
//        return ret;
//    }
//};



//class MyQueue {
//public:
//    MyQueue() {
//
//    }
//
//    void push(int x) {
//        pushSt.push(x);
//    }
//
//    int pop() {
//        peek();
//        int ret = popSt.top();
//        popSt.pop();
//        return ret;
//    }
//
//    int peek() {
//        if (popSt.empty()) {
//            while (!pushSt.empty()) {
//                popSt.push(pushSt.top());
//                pushSt.pop();
//            }
//        }
//        return popSt.top();
//    }
//
//    bool empty() {
//        return popSt.empty() && pushSt.empty();
//    }
//private:
//    stack<int> popSt;
//    stack<int> pushSt;
//};




//class MyStack {
//public:
//    MyStack() {
//
//    }
//
//    void push(int x) {
//        if (q1.empty()) q2.push(x);
//        else q1.push(x);
//    }
//
//    int pop() {
//        int ret = 0;
//        if (q1.empty()) {
//            while (q2.size() > 1) {
//                q1.push(q2.front());
//                q2.pop();
//            }
//            ret = q2.front();
//            q2.pop();
//        }
//        else {
//            while (q1.size() > 1) {
//                q2.push(q1.front());
//                q1.pop();
//            }
//            ret = q1.front();
//            q1.pop();
//        }
//        return ret;
//    }
//
//    int top() {
//        return q1.empty() ? q2.back() : q1.back();
//    }
//
//    bool empty() {
//        return q1.empty() && q2.empty();
//    }
//private:
//    queue<int> q1;
//    queue<int> q2;
//};



//class MyStack {
//public:
//    MyStack() {
//
//    }
//
//    void push(int x) {
//        q.push(x);
//    }
//
//    int pop() {
//        int sz = q.size() - 1;
//        while (sz--) {
//            q.push(q.front());
//            q.pop();
//        }
//        int ret = q.front();
//        q.pop();
//        return ret;
//    }
//
//    int top() {
//        return q.back();
//    }
//
//    bool empty() {
//        return q.empty();
//    }
//private:
//    queue<int> q;
//};





//class Solution {
//public:
//    bool isValid(string s) {
//        stack<int> st;
//        for (auto ch : s) {
//            if (ch == '(' || ch == '[' || ch == '{') st.push(ch);
//            else
//            {
//                if (st.empty() || (ch == ')' && st.top() != '(')
//                    || (ch == ']' && st.top() != '[')
//                    || (ch == '}' && st.top() != '{'))
//                    return false;
//                st.pop();
//            }
//        }
//        return st.empty();
//    }
//};





//class Solution {
//public:
//    string removeDuplicates(string s) {
//        vector<char> st;
//        for (auto ch : s) {
//            if (!st.empty() && st.back() == ch) {
//                st.pop_back();
//            }
//            else {
//                st.push_back(ch);
//            }
//        }
//        return string(st.begin(), st.end());
//    }
//};




//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        if (tokens.size() == 0) return 0;
//        unordered_map<string, function<int(int, int)>> opHash = {
//            {"+", [](int x, int y) { return x + y; }},
//            {"-", [](int x, int y) { return x - y; }},
//            {"*", [](int x, int y) { return x * y; }},
//            {"/", [](int x, int y) { return x / y; }}
//        };
//
//        stack<int> st;
//        for (auto& str : tokens) {
//            if (opHash.find(str) == opHash.end()) {
//                st.push(stoi(str));
//            }
//            else {
//                int y = st.top(); st.pop();
//                int x = st.top(); st.pop();
//                st.push(opHash[str](x, y));
//
//            }
//        }
//        return st.top();
//    }
//};



